#define _CRT_SECURE_NO_WARNINGS 1




//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
// 
//
//int kthToLast(struct ListNode* head, int k)
//{
//	struct ListNode* cur = head;
//	int num = 0;
//
//	while (cur)
//	{
//		++num;
//		cur = cur->next;
//	}
//
//	int m = num - k + 1;
//	cur = head;
//
//	while (--m)
//	{
//		cur = cur->next;
//	}
//
//	return cur->val;
//}




//#include <stdio.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
//
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//	struct ListNode* curA = headA;
//	struct ListNode* curB = headB;
//
//	while (curA)
//	{
//		curB = headB;
//
//		while (curB)
//		{
//			if (curA == curB)
//			{
//				return curA;
//			}
//
//			curB = curB->next;
//		}
//
//		curA = curA->next;
//	}
//
//	return NULL;
//}



//#include <stdio.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
//
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//	struct ListNode* curA = headA;
//	struct ListNode* curB = headB;
//	struct ListNode* prevA = NULL;
//	struct ListNode* prevB = NULL;
//	int nA = 0;
//	int nB = 0;
//
//	while (curA)
//	{
//		++nA;
//		prevA = curA;
//		curA = curA->next;
//	}
//
//	while (curB)
//	{
//		++nB;
//		prevB = curB;
//		curB = curB->next;
//	}
//
//	if (prevA != prevB)
//	{
//		return NULL;
//	}
//
//	int sub = nA - nB;
//	curA = headA;
//	curB = headB;
//
//	if (sub < 0)
//	{
//		sub = -sub;
//
//		while (sub--)
//		{
//			curB = curB->next;
//		}
//	}
//	else
//	{
//		while (sub--)
//		{
//			curA = curA->next;
//		}
//	}
//
//	while (curA != curB)
//	{
//		curA = curA->next;
//		curB = curB->next;
//	}
//
//	return curA;
//}




#include <stdio.h>
#include <stdbool.h>

typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;

struct ListNode* middleNode(struct ListNode* head)
{
	ListNode* slow, * fast;
	slow = fast = head;

	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	return slow;
}

struct ListNode* reverseList(struct ListNode* head)
{
	if (NULL == head)
	{
		return head;
	}

	ListNode* n1, * n2, * n3;
	n1 = NULL, n2 = head, n3 = head->next;

	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;

		if (n3)
		{
			n3 = n3->next;
		}
	}

	return n1;
}

bool chkPalindrome(ListNode* A)
{
	ListNode* mid = middleNode(A);
	ListNode* rmid = reverseList(mid);

	while (A && rmid)
	{
		if (A->val != rmid->val)
		{
			return false;
		}

		A = A->next;
		rmid = rmid->next;
	}

	return true;
}